#pragma once

namespace jianzhi_044
{

class Solution
{
public:
    int findNthDigit(int n)
    {
        if (n < 10)
            return n;

        int digits_width = 1;
        long long digits_before = 10;
        long long base = 10;

        while (n >= digits_before) {
            ++digits_width;
            digits_before += (base * 10 - base) * digits_width;
            base *= 10;
        }

        base /= 10;
        digits_before -= (base * 10 - base) * digits_width;
        int num = (n - digits_before) / digits_width + base;
        int pos = (n - digits_before) % digits_width;

        for (int i = 0; i < digits_width - pos - 1; ++i)
            num /= 10;
        return num % 10;
    }
};

}  /* namespace jianzhi_044 */
